#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

    int numTrees(int n) {
	if ( n == 0 || n == 1) return 1;
	if (n == 2) return 2;
	int cnt = 0;
	for (int i = 0; i < n; i++) {
	   cnt += numTrees(i) * numTrees(n-i-1); 
	}
	return cnt;
    }

int main(int argc, char **argv)
{
    cout << numTrees(3);
    cout << "-----------------Test 1--------------------" << endl;


    cout << "-----------------Test 2--------------------" << endl;


    cout << "-----------------Test 3--------------------" << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
